The present invention relates generally to computer systems, and more particularly, to rendering volumetric data to produce a two-dimensional image.
Many physical objects can be represented spatially and temporally by computerized models. Scaler and vector volumetric data representing the structures or features of such objects can be generated empirically by using medical scanners, seismic survey, sonar, radar, and the like. Volumetric data can also be synthetically generated by computerized models. Objects represented can include the internal structure of atoms, the distribution of background radiation in the universe, or even imaginary objects.
Computer generated images produced with the volumetric data find utility in computer-aided design, and in scientific and medical visualization fields. A two-dimensional (2D) image perceived as a three-dimensional (3D) presentation can convey large amounts of information in a more comprehensible form than is possible using other traditional techniques such as statistical tables or voluminous prose. Translucent volume rendering or images representing a selected plane or slice through an object are especially helpful for studying internal structures, and for visually relating the interior of objects to their external forms.
Images presented in an animated sequence can take advantage of motion parallax for better morphological understanding of the object represented by the volumetric data. Currently, on most computer systems, the time required to generate 2D images from volumetric data is too long to support real-time generation rates and manipulation. If the images are generated too slowly, the viewer""s attention lapses, thought processes are disrupted, and the significance of differences between successive frames of the image is lost.
In volume rendering, a volume element or xe2x80x9cvoxelxe2x80x9d is the 3D equivalent of a 2D pixel, or picture element. Voxels are usually organized into a parallelpiped arrangement relative to some Cartesian coordinate system. Each voxel represents a quantum data unit of the volume. The voxel can have associated scaler or vector values symbolizing some property of the portion of the object in the immediate vicinity of the corresponding voxel.
To view an object represented by volumetric data, the values are mapped into pixels in the image plane. For the purpose of viewing, the data of the voxel data are usually expressed abstractly in terms of color and opacity. Color may be used to differentiate a particular object property, such as density or heat distribution, and the opacity of the color may indicate the relative intensity of the differentiation. For a given orientation of the object, the Cartesian grid of the volume data may not always align perfectly with the Cartesian grid of the image plane. Various techniques are known for deriving the value of the 3D space between adjacent voxels, for example, tri-linear interpolation.
The techniques of volume rendering can be categorized as either geometric iso-surface rendering, or direct volume rendering. Geometric iso-surface rendering converts the 3D data into geometry, usually polygons which can be displayed using traditional imaging techniques. However, other than for simple objects, substantial processing is usually required to extract the iso-surfaces.
Direct volume rendering, on the other hand, utilizes the entire original generated volumetric data in the final rendering of the image, and thus any part, including the interior of the object can be viewed by mapping the 3D voxels onto the 2D pixels. Two mapping techniques, forward and backward mapping, are commonly used for direct volume rendering.
In forward, or object space mapping, the 3D voxels are projected onto the 2D pixels of the image plane. Backward, or image space mapping places an imaginary viewer and an imaginary image plane in the three-dimensional environment of the object. The composition of the scene on the image plane is determined by casting imaginary rays through the pixels of image plane to traverse the volumetric data. The color and opacity of the volumetric data encountered approximately along the trajectory or path of the ray are interpolated, and integrated, usually at regularly spaced intervals to determine the colors and opacities of the pixels.
In general, ray-casting is well suited for manipulation by computer systems having massively parallel architectures. Massively parallel computers have a plurality of processor elements (PEs), each PE having access to an associated memory. Massively parallel computers are categorized as either Multi-Instruction Multiple-Data (MIMD), or Single-Instruction Multiple-Data (SIMD).
One of the main differences between MIMD and SIMD architectures is that the instruction stream is the same for each PE of a SIMD computer, whereas the instructions for the PEs of a MIMD computer can be different. In other words, MIMD computers can be considered extensions of uni-processors with each PE working on some portion of the total work-load. Typically, jobs are parceled out serially to the PEs as they become idle, with minimal attention paid to synchronizing the PEs.
On the other hand, in a SIMD computer, each PE is manipulating different data while constrained to execute the same instruction in a lock-step manner. Processes used by SIMD computers are sometimes called xe2x80x9cdata-parallel processesxe2x80x9d since the parallelism is on the data, and not the executed instructions. As an advantage, SIMD computers can be provided with a substantially larger number of processor elements than comparably priced MIMD computers. For example, SIMD computers having thousands of PEs are readily available, while MIMD computers of a similar price typically include less than a hundred PEs.
Keeping many thousands of PEs busy, as will be discussed herein, is a non-trivial problem. Unless the work load is carefully balanced among the processors, the efficiencies gained by the high degree of parallelism are quickly lost. Since the SIMD architecture requires that all active processors, at any one time, execute the same instruction, inactive processors remain stalled until active processors have completed a current set of instructions. Therefore, while implementing applications for SIMD computers, the data structures and processes which manipulate the data must be especially designed in order to maximize processing parallelism.
In one known data-parallel implementations, the volumetric data are oriented so a particular processor element can find all of the data for determining color and opacity values of a particular ray within its associated memory. In more detail, the volumetric data are first distributed among the local memories of each PE according to each ray cast. The goal is to have each PE cast a complete ray through the volumetric data stored in its associated memory, from start to finish. The required accumulation of pixel values, e.g., color and opacity, for a single ray are all performed within a single PE. Obviously, for a stationary viewing angle this technique is fairly efficient.
However, difficulties arise if the viewer desires to manipulate the represented object to view multiple orientations. To accomplish this in the prior art, the volumetric data are routed from PE to PE by a series of shears to align the data with a particular viewing angle. In addition to taking a considerable amount of time, multiple sheers tend to introduce progressively more observable artifacts into the final image as a result interpolation errors after shearing to reconstruct the Cartesian grid of the voxels.
Another data parallel volume rendering technique is based on object parallelism. That is, for a given set of data stored in a single processor, only the values of the intersecting rays are computed. Here, the volumetric data are only reoriented if the angle of rotation is greater than 45 degrees with respect to a Cartesian axes of the volumetric data. Once the volumetric data are in place, for any given viewing orientation that does not exceed 45 degrees from the original viewing orientation of the data, rays are cast into the volumetric data. Each PE stores adjacent columns or slices of data. If a particular ray stays within a slice, all data can be obtained from a single PE. Otherwise, if the orientation of the ray strays out of the bounds of the slice of data, the partial values of the ray are shifted to a neighboring PE for continued computation. In order to have all PEs shift their rays synchronously, the rays are not necessarily cast from their position on the image plane. Rather, the rays are spaced at the same offset as the voxels. By originating rays at an offset equal to the spacing between the voxels, parallel rays cross voxel boundaries at the same time, resulting in high processor utilization. However, to create the final image, the ray values must be reinterpolated to obtain the value of the pixel. Interpolation tends to introduce annoying artifacts in the image.
A closely related object parallel algorithm exists in the MIMD domain of massively parallel computers. Computers built according to the MIMD architecture are not constrained by the lock-step instruction cycles characteristic of SIMD processors. In a hybrid image partition-ray data flow technique of parallel ray casting, ray values are only computed when rays are cast through data within the spatial bounds of a particular processor. As an advantage, in MIMD architecture, rays do not need to be spaced at the same offset as the voxels. Therefore, reinterpolation of the ray values to produce the image is not required. However, as stated earlier, MIMD computers are relatively expensive when compared with SIMD computers having a substantially greater number of processors.
From the foregoing, it is apparent that there is a need for a technique which permits rapid volumetric data rendering. It is desired that the technique enables interactive visualization of represented objects without diminishing the quality of the rendered image. It is to these ends the present invention is directed.
A system and method are provided for interactively visualizing a real or imaginary object represented by three-dimensional or volumetric data. The volumetric data, which may be empirically or synthetically generated, are composed of values or voxels. The voxels are projected onto a two-dimensional image plane having a plurality of pixels. The visualization, in part, is achieved by organizing the volumetric data into a plurality of blocks of data, each block of data including a plurality of voxels arranged in parallelpiped structure. Each block of volumetric data is stored in, and processed by a particular processor element of a massively data-parallel computer system having a plurality of processor elements.
After the blocks of volumetric data are fixed in the associated processor elements, the volumetric data may be rendered for any viewing angle, without any further rearrangement of the volumetric data. Preferably, a plurality of rays are cast through the image plane to traverse the volumetric data. The rays are preferably normal to the image plane for a given viewing angle. There is one ray for each pixel of the image plane. That portion of a particular ray which traverses a particular block of data is called a ray segment. The volumetric data approximately along the path of the ray segments are interpolated, and integrated at regularly spaced intervals.
The object can be rendered, at a higher degree of parallelism, by performing phased processes on the volumetric data. Rendering can be performed for any viewing angle without requiring the data to be routed to different processor elements. In addition, the image can be produced without reinterpolating the volumetric data thus avoiding undesirable artifacts.
In a ray collection phase, each processor element, in parallel with the other processor elements, determines which sub-set of ray segments traverse the associated block of data. The sub-sets of ray segments are determined by projecting the faces of the associated block of data onto the image plane.
In a segment combining phase, each processor element, in parallel with the other processor elements, determines the integrated contribution of the interpolated values for the sub-set of ray segments traversing its block of data.
In a final accumulation phase, the segment values of each entire ray are accumulated in order to determine the value of the associated pixels.